This invention relates to address generation and modification in computer programs.
In a software data structure, a pointer is an identifier (e.g., a variable) that indicates the location (e.g., holds the address) of an item of data. When the data structure is moved from place to place in memory or between machines, the addresses of the data structure change. Therefore, pointers in data structures cannot be saved and restored to arbitrary memory locations or transferred between processes or servers without adjustment or special conversion. In general, the adjustment/conversion is a two step process: first, convert the pointers in the data structure to base-relative (i.e., relative to the address of the first location of the data structure) or to another data type; then, store or send the new (modified) data structure. The operation is reversed when loading or receiving a data structure.
The standard adjustment/conversion process uses a base address and an offset. The process converts all the pointers in the data structure to an address relative to this base address. This technique requires searching the data structure, and fixing the pointers. This means that each type of data structure requires a specification for conversion. An alternative technique is to change the pointers in the data structure to base-relative offsets. This solves the loading and saving problem, but requires maintaining and managing the base pointers specific to each and every data structure. When the relative pointer is passed to a function, the base pointer must also be passed, so the basic program structure is more complicated.
The problems with these methods are performance and complexity. Searching a data structure to convert it for sharing or storage is expensive. Maintaining a base pointer and always adding it to each offset pointer is tedious, requires more code, and requires wrapper modules or globals to handle the base pointer.
When multiple shared memory blocks or shared network objects contain linked pointers, the inter-process conversion routines must translate all of the addresses from one process space to another. This puts a practical limitation on the complexity of objects that can be easily shared between processes or servers. For example, a large linked list (like a hash table) being sent from one server to another must be converted twice, thereby requiring twice the intermediate storage space and possibly long conversion times.
Yet another problem with current pointer arrangements is encountered when moving from a 32-bit operating system to a 64-bit operating system, such as Microsoft""s NT 64. The conventional pointers do not work in the new operating system, because pointers and offsets become 64-bit entities. So all 32-bit offsets must be manually found and typecast correctly to unsigned 64-bit numbers.
This invention is directed to solving these and other problems and disadvantages of the prior art. Generally according to the invention, an auto (i.e., self)-relative pointer defines a pointed-to location by means of an offset from its own location. In other words, the address of the pointer is offset by the value of the pointer to obtaining the address of the pointed-to location.
According to one aspect of the invention, a method of defining a pointer to a location comprises the steps of determining an offset of a location of the pointer from a location that the pointer is to point to, and storing the offset as a value of the pointer in the location of the pointer. According to another aspect of the invention, a method of determining a location pointed to by a pointer comprises the steps of retrieving from a location of the pointer a value of the pointer, and using the retrieved value as an offset from the location of the pointer to identify the location pointed to by the pointer. While the methods comprise the steps of the just-characterized procedures, another aspect of the invention embraces apparatuses that effect the method steps. Each apparatus preferably includes an effectorxe2x80x94any entity that effects the corresponding step, unlike a meansxe2x80x94for each step.
Simplicity is the biggest advantage of the invention over the prior art. There is no pointer conversion. Data structures built with autorelative pointers can be used in inter-process and/or inter-server communications without conversion. Auto-relative pointers can be placed in shared memory, stored on disk, and moved from one part of memory to another, without translation or tracking of the base address. The invention makes it easy to build a relative pointer class (e.g., in C++) with all the features of normal pointers, while providing fast and easy de-referencing without a base pointer. Because of the simplicity, errors are easier to avoid and to find. This technique is faster, compilers can optimize it easier, and it produces more efficient code than base-relative pointer techniques. Very complex objects can be passed between processes and over networks without special conversion and extra intermediate memory storage. Structures do not require a mapping specification for automatic (inter-process) conversion.
Furthermore, the invention solves the pointer problem encountered in going from a 32-bit operating system to a 64-bit operating system. Unlike in the prior art, the offsets do not need to be manually converted to 64-bit numbers, because all of the auto-relative pointers can be assigned to the same class or group, and then typecasting of the pointers is done once for the whole class or group.